package com.lili.other;

/**
 * @Auther: 李 力
 * @Date: 2024/8/23
 * @Description: 1206. 设计跳表
 * @version: 1.0
 */
public class Skiplist {
    static final int MAX = 4;

    static int randomLevel() {
        int level = 1;
        while (Math.random() < 0.5 && level < MAX) {
            level++;
        }
        return level;
    }

    private final Node head = new Node(-1);

    static class Node {
        int val;
        Node[] next;

        public Node(int val) {
            this.val = val;
            this.next = new Node[MAX];
        }
    }

    private Node[] find(int val) {
        Node[] path = new Node[MAX];
        Node curr = head;
        for (int lvl = MAX - 1; lvl >= 0; lvl--) {
            while (curr.next[lvl] != null && curr.next[lvl].val < val) {
                curr = curr.next[lvl];
            }
            path[lvl] = curr;
        }
        return path;
    }

    public boolean search(int val) {
        Node[] path = find(val);
        Node node = path[0].next[0];
        return node != null && node.val == val;
    }

    public void add(int val) {
        Node[] path = find(val);
        int lv = randomLevel();
        Node node = new Node(val);
        for (int i = 0; i < lv; i++) {
            node.next[i] = path[i].next[i];
            path[i].next[i] = node;
        }
    }

    public boolean erase(int val) {
        Node[] path = find(val);
        Node node = path[0].next[0];
        if (node == null || node.val != val) {
            return false;
        }
        for (int i = 0; i < MAX; i++) {
            if (path[i].next[i] != node) {
                break;
            }
            path[i].next[i] = node.next[i];
        }
        return true;
    }
}
